[AI] [BFS] Demo code thuật toán BFS bằng Javascript

Hello mọi người nha, lâu nay mình vẫn xem chùa mà hôm nay rảnh quá nên muốn làm một series về các thuật toán AI cho mọi người. Hôm nay mình sẽ làm 1 demo về thuật toán BFS nha !

Tổng quan về thuật toán BFS

Bây giờ mà nói về cái thuật toán này thì dài lắm, nên mình trích dẫn vài cái link cho những ai chưa rõ về lý thuyết thì tìm hiểu nha :
Wikipedia


lhchuong

Thuật toán

function BFS(start,end){
  var open = []; //chứa các đỉnh đang xét
  var close = []; //chứa các đỉnh đã xét
  var edge; //đỉnh được xét hiện tại
  var dependent = []; //tập các đỉnh kề với edge
  open.push(start); //cho start vào cuối danh sách open
  //lặp khi open không rỗng
  while(open.length > 0){
    edge = open[0]; //lấy đỉnh đầu của danh sách open
    open.shift(); //xóa phần tử edge khỏi danh sách open
    if(edge == end){
      return true; //đã tìm thấy
    }
    open.push(dependent(edge));//cho tập dependent vào cuối danh sách open
    close.push(edge);//cho edge vào cuối danh sách đóng
  }
}

Code example

Đầu tiên thì mình cho các bạn xem cái map mình làm sẵn để minh họa, thuật toán BFS sẽ giúp chúng ta tìm ra đường đi giữa các vị trí trong map.
map


Map dạng bàn cờ (4*4) , tọa độ các thứ :v


tree_map


Map dạng biểu đồ cây

Map code

Mình sẽ trình bày các map trên dưới dạng code nha !

//Hình 1
let map = {
  "a0" : ["b0","a1"],
  "a1" : ["a0","a2"],
  "a2" : ["a1","b2"],
  "a3" : "block",
  "b0" : ["a0","c0"],
  "b1" : "block",
  "b2" : ["a2","b3","c2"],
  "b3" : ["b2","c3"],
  "c0" : ["b0","c1"],
  "c1" : ["c0","d1","c2"],
  "c2" : ["c1","b2","c3"],
  "c3" : ["c2","b3","d3"],
  "d0" : "block",
  "d1" : ["c1"],
  "d2" : "block",
  "d3" : ["c3"]
}
//Hình 2 (tree)
let map2 = {
  "A" : ["B","C","D"],
  "B" : ["M","N"],
  "C" : ["L"],
  "D" : ["O","P"],
  "M" : ["X","Y"],
  "N" : ["U","V"],
  "O" : ["I","J"],
  "Y" : ["R","S"],
  "X" : [],
  "L" : [],
  "P" : [],
  "U" : [],
  "V" : ["G","H"],
  "I" : [],
  "J" : [],
  "R" : [],
  "S" : [],
  "G" : [],
  "H" : [],
}

Như các bạn thấy thì code này là 1 object, trong đó mỗi phần tử tương đương với 1 đỉnh(edge) và giá trị của nó là 1 array chứa các đỉnh kề nó, trong trường hợp 1 sẽ loại bỏ các block(tô đỏ - đóng vai trò là vật cản) ra nha !

Code

Tham số đầu vào sẽ là điểm startend mà bạn muốn tìm đường.


Đầu tiên ta khởi tạo 2 array openclose để,...

let open = [];  //chứa các đỉnh đang xét
let close = []; //chứa các đỉnh đã xét

Đẩy điểm start vào cuối danh sách open

open.push(start);

Tạo 1 object List để lưu trữ các thao tác duyệt, về sau muốn tìm được đường cũng phải nhờ thằng List này đấy =))

let list = {};

Thêm phần tử đầu tiên vào List , cấu trúc của nó bao gồm heightchiều cao phần tử đưa vào List ở trong cây, bắt đầu từ 0, phần tử start là nơi ta muốn bắt đầu nên nó không có phần tử cha => parent = null

list[start] = {
    height : 0,
    parent : null
};

Một function dependent để lấy ra danh sách các đỉnh(edge) kề của đỉnh muốn xét, đồng thời với đó nó sẽ đưa vào trong List danh sách duyệt.

let dependent = function(e){
    let result = map[e];
    for(let i=0;i<result.length;i++){
      if(list[result[i]] == undefined){
        list[result[i]] = {
          height : list[e].height + 1,
          parent : e
        };
      }
    }
    return result;
 }

Một function pushDependentToEndOfOpen để đẩy các dependent vào danh sách open

function pushDependentToEndOfOpen(dpd,openList){
    for(let i=0;i<dpd.length;i++){
      openList.push(dpd[i]);
    }
}

Một vòng lặp while để duyêt các phần tử trong danh sách open

 while(open.length > 0){ //khi open không rỗng
    let edge = open[0];  //lấy ra phần tử muốn duyệt ở đầu danh sách open
    open.shift();     //lấy ra rồi thì phải xóa ở trong open đi để còn duyệt tiếp :v
    if(edge == end){  //khi tìm thấy rồi thì...
         return HandleWhenFound(); //function xử lí khi tìm thấy, xem sau nhé =))
    }
    pushDependentToEndOfOpen(dependent(edge),open); //đẩy dependent vào open
    close.push(edge);  //đẩy edge duyệt ok rồi vào close
 }

Function xử lý khi tìm thấy end nà :v , kèm luôn 1 function lấy đường đi nhá

let way = function(list){
    let result = [];
    let edge = end;
    result.unshift(edge);
    while(list[edge].parent != null){
      edge = list[edge].parent;
      result.unshift(edge);
    }
    return result; 
}
function HandleWhenFound(){
    return {
       way : way(list),
       list : list
    }
}

How to chạy =))

//map1
let result = BFS("a0","d3",map);
console.log(result.way);
console.log(result.list);
//map2
let result2 = BFS("A","U",map2);
console.log(result2.way);
console.log(result2.list);

Kết

OK, vậy là phần 1 trong series demo AI về BFS kết thúc ở đây. Code ở trên nếu mọi người chưa hiểu có thể xem full source mình up lên trên github tại Đây.Mọi người xem nếu thích thì like follow các kiểu nha :v, lấy động lực mình lại ra tiếp các phần sau =)). Có gì sai sót mn có thể report cho mình tại issue nha.Thank all !

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

phuong

1 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Bài viết liên quan
White
4 0
Nhằm đáp ứng nhu cầu công việc của team AI, nên gần đây mình cần tìm hiểu về Tensorflow. Trong chuỗi blog này mình xin chia sẻ về những kiến thức m...
Kaopiz Software Co., Ltd. viết 5 tháng trước
4 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
1 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!