HomeLập trìnhJavaScriptCách sử dụng...

Cách sử dụng phương thức Map() của JavaScript để giải quyết vấn đề tìm kiếm theo chiều rộng và theo chiều sâu


JavaScript map() phương thức là một đối tượng có cặp khóa và giá trị. Khóa và giá trị của một đối tượng được kết nối bằng dấu hai chấm (:) trong khi khóa và giá trị của bản đồ được kết nối bằng mũi tên (=>).

Đây là một ví dụ về một đối tượng trong JavaScript:

{ a: [ 1, 2, 3 ], b: 2, c: 3 }
Đối tượng JavaScript

Và đây là một ví dụ về bản đồ trong JavaScript:

{ 'a' => [ 1, 2, 3 ], 'b' => 2, 'c' => 3 }
Bản đồ JavaScript

Các map() phương pháp là một công cụ tốt để giải quyết các vấn đề về thuật toán và cấu trúc dữ liệu như đồ thị, khoảng cách ngắn nhất và tuyến đường tốt nhất. Nhiều công ty vận tải đã sử dụng phương pháp này để xây dựng ứng dụng của họ. Chúng tôi sẽ làm một cái gì đó như thế trong hướng dẫn này.

Tôi đã thêm video vào cuối các phần khác nhau của hướng dẫn này dành cho những người thích hướng dẫn trực quan hơn.

Mục tiêu của bài viết này

Hướng dẫn này nhằm mục đích dạy cho bạn cách map() phương pháp hoạt động và cách bạn có thể sử dụng nó khi giải các bài toán tìm kiếm Hơi thở và Tìm kiếm theo chiều sâu.

Cuối cùng, bạn sẽ học được những điều cơ bản của map() và bạn sẽ thấy một góc nhìn khác trong việc giải quyết các vấn đề về thuật toán và cấu trúc dữ liệu như đồ thị, tìm kiếm theo chiều rộng (BFS) và tìm kiếm theo chiều sâu (DFS).

điều kiện tiên quyết

Hướng dẫn này giả định rằng bạn đã làm việc với các khái niệm Javascript cơ bản như chuỗi, mảng, đối tượng và tập hợp. Nó cũng có thể hữu ích để đọc về các thuật toán và cấu trúc dữ liệu.

Hãy lên đường!

Vấn đề

Nigeria có 36 tiểu bang. Một khách du lịch có thể di chuyển từ trạng thái này sang trạng thái khác bằng đường bộ, đường hàng không và đường thủy được gọi là tuyến đường. Những gì chúng tôi muốn làm là lập trình:

  1. Hiển thị từng trạng thái và các trạng thái khác được kết nối với nó trong biểu đồ.
  2. Kiểm tra xem bạn có thể kết nối hai (2) trạng thái không.

Vì vậy, chúng tôi được cung cấp mười một (11) trong số ba mươi sáu (36) tiểu bang của Nigeria để hợp tác với:

ENUGU, ABIA, SOKOTO, NIGER, LAGOS, OGUN, BAYELSA, AKWAIBOM, ANAMBRA, IMO, EBONYI

Đây là các tuyến đường:

  • ENUGU đến LAGOS
  • ENUGU đến NIGER
  • NIGER đến SOKOTO
  • NIGER đến ANAMBRA
  • SOKOTO đến ANAMBRA
  • OGUN đến LAGOS
  • OGUN đến ABIA
  • OGUN sang EBONYI
  • OGUN đến BAYELSA
  • EBONYI đến ABIA

Hãy sử dụng những dữ liệu này để giải quyết vấn đề!

Làm thế nào để giải quyết vấn đề

Trong phần trước, chúng ta đã thấy vấn đề. Bây giờ chúng ta sẽ giải quyết vấn đề đó ở đây. Tôi sẽ sử dụng Replit cho hướng dẫn này.

Replit cung cấp cho bạn một IDE được trang bị tốt để viết và kiểm tra nhanh các chương trình giống như chương trình chúng tôi sắp viết.

Cách thiết lập bản đồ

Vấn đề đầu tiên chúng tôi muốn giải quyết là lập trình hiển thị từng trạng thái và các trạng thái khác được kết nối với nó.

Bắt đầu bằng cách xác định mười một (11) trạng thái và lộ trình của chúng. Nhập mã sau đây:


const states="ENUGU ABIA SOKOTO NIGER LAGOS OGUN BAYELSA AKWAIBOM ANAMBRA IMO EBONYI".split(' ');

const routes = [
  ['ENUGU', 'LAGOS'],
  ['ENUGU', 'NIGER'],
  ['NIGER', 'SOKOTO'],
  ['NIGER', 'ANAMBRA'],
  ['SOKOTO', 'ANAMBRA'],
  ['OGUN', 'LAGOS'],
  ['OGUN', 'ABIA'],
  ['OGUN', 'EBONYI'],
  ['OGUN', 'BAYELSA'],
  ['EBONYI', 'ABIA'],
];

Tạo một cái mới map() hoặc đồ thị có tên connections:

const connections = new Map();

Tiếp theo, nhập mã sau đây:

states.forEach((state) => {
  connections.set(state, []);
});

Mã này lặp qua tất cả các Những trạng thái. Nó lấy từng trạng thái và đặt nó làm khóa trong connections biểu đồ với giá trị mặc định của một mảng trống ([]).

Đọc thêm  Phương thức reduce và reduceRight của JavaScript hoạt động như thế nào

nếu bạn đăng nhập connections vào giao diện điều khiển, bạn sẽ nhận được kết quả như sau:

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}

Hiện tại, hãy hình dung biểu đồ ở đầu ra ở trên giống như trong hình bên dưới:

Ảnh chụp màn hình-2022-08-10-at-16.44.32
Biểu diễn đồ họa của các quốc gia đã cho

Nhập mã dưới đây:

routes.forEach(route => {
  const departure = [...route][0];
  const destination = [...route][1];
  
  connections.get(departure).push(destination);
  connections.get(destination).push(departure);
});

Mã này thêm các trạng thái vào các giá trị mảng trống của các khóa ở bước trước. Nó khoanh tròn qua mảng các tuyến đường và trích xuất từng tuyến đường.

Trạng thái khởi hành được đặt thành mục đầu tiên trong mảng tuyến đường, trong khi trạng thái đích là trạng thái thứ hai.

Sau đó, nó thêm trạng thái đích vào giá trị mảng của trạng thái khởi hành. Cuối cùng, trạng thái khởi hành được bao gồm trong giá trị mảng của trạng thái đích.

Tại thời điểm này, nếu bạn đăng nhập connections vào giao diện điều khiển, bạn sẽ nhận được kết quả như sau:

Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}

Loại đồ thị này là vô hướng. Đồ thị vô hướng là một loại đồ thị mà bạn có thể di chuyển từ nút đến (các) cạnh và từ (các) cạnh quay lại nút. Trong trường hợp của chúng tôi, nút là trạng thái khởi hành, trong khi (các) cạnh là trạng thái đích.

Sau đây là một đại diện bằng hình ảnh của đầu ra ở trên:

Ảnh chụp màn hình-2022-08-10-at-16.29.30
Một đồ thị vô hướng đại diện cho các tuyến đường

Đầu mũi tên có tô màu đen trỏ đến trạng thái đích, trong khi đầu mũi tên có tô màu trắng trỏ đến trạng thái khởi hành.

Để làm cho biểu đồ này được định hướng, thay vào đó, bạn có thể sử dụng mã này:

routes.forEach(route => {
  connections.get([...route][0]).push([...route][1]);
});

Đây là đầu ra dưới đây:

Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [],
  'SOKOTO' => [ 'ANAMBRA' ],
  'NIGER' => [ 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => [ 'ABIA' ]
}

Sau đây là một đại diện bằng hình ảnh của đầu ra ở trên:

Ảnh chụp màn hình-2022-08-10-at-16.06.57
Đồ thị có hướng biểu diễn các tuyến đường

Nếu cảm thấy khó hiểu, hãy nghiên cứu các kết quả đầu ra và so sánh chúng với các lộ trình đã cho. Mã sẽ trở nên dễ dàng hơn khi bạn thực hành.

Chúng tôi đã có thể chỉ ra cách các trạng thái này được kết nối theo chương trình. Xem mã trông như thế nào cho đến nay:


const states="ENUGU ABIA SOKOTO NIGER LAGOS OGUN BAYELSA AKWAIBOM ANAMBRA IMO EBONYI".split(' ');

const routes = [
  ['ENUGU', 'LAGOS'],
  ['ENUGU', 'NIGER'],
  ['NIGER', 'SOKOTO'],
  ['NIGER', 'ANAMBRA'],
  ['SOKOTO', 'ANAMBRA'],
  ['OGUN', 'LAGOS'],
  ['OGUN', 'ABIA'],
  ['OGUN', 'EBONYI'],
  ['OGUN', 'BAYELSA'],
  ['EBONYI', 'ABIA'],
];

const connections = new Map();

states.forEach((state) => {
  connections.set(state, []);
});

console.log(connections)

routes.forEach(route => {
  const departure = [...route][0];
  const destination = [...route][1];
  
  connections.get(departure).push(destination);
  connections.get(destination).push(departure);
});

console.log(connections)

Chúng tôi đang chuyển sang phần tiếp theo của vấn đề (để kiểm tra xem bạn có thể kết nối hai (2) trạng thái hay không.). Chúng tôi sẽ thực hiện theo hai (2) cách. Đầu tiên, chúng ta sẽ khám phá thuật toán tìm kiếm theo chiều rộng, sau đó chúng ta sẽ thực hiện nó bằng cách sử dụng cách tìm kiếm theo chiều sâu.

BFS là một thuật toán được sử dụng để kiểm tra một cây hoặc đồ thị bằng cách khám phá các con trực tiếp (các cạnh) của nút cha (nút) trước khi chuyển sang các cháu. Nó tiếp tục theo cách đó cho đến hết cây hoặc biểu đồ.

Ví dụ: trong trường hợp của chúng tôi, giả sử chúng tôi muốn kiểm tra xem có thể có kết nối giữa ENUGU và ABIA hay không.

BFS sẽ bắt đầu từ Enugu và kiểm tra tất cả các tuyến đường trực tiếp của Enugu (LAGOS và NIGER). Do ABIA không được kết nối trực tiếp với ENUGU nên thuật toán sẽ chuyển sang kiểm tra (các) trạng thái được gắn với LAGOS.

Đọc thêm  Cách hiểu từ khóa này và ngữ cảnh trong JavaScript

Tiếp theo, thuật toán sẽ kiểm tra (các) trạng thái được liên kết với NIGER. Quá trình sẽ tiếp tục cho đến khi tìm thấy ABIA hoặc gặp ngõ cụt. Điều đó chấm dứt chương trình.

BFS sử dụng cấu trúc dữ liệu hàng đợi. Điều đó có nghĩa là các mục sẽ được nhập từ đầu này và xóa từ đầu kia của mảng. Trong trường hợp của chúng tôi, hàng đợi sẽ chứa tất cả các trạng thái chưa được truy cập. Khi chúng tôi tiếp tục xây dựng chương trình, bạn sẽ thấy nó hoạt động.

Hãy bắt đầu xây dựng BFS bằng cách tạo một hàm có tên bfs:

function bfs(departureState, destinationState) {

}

Hàm này nhận hai (2) đối số, departureStatedestinationState.

Bên trong chức năng, xác định một queue và thêm departureState trong đó:

  const queue = [departureState];

Chúng tôi đang thêm departureState đến queue mảng vì nó chứa tất cả các nút chưa được thăm.

Tiếp theo, xác định một khoảng trống mới Set() đặt tên visited:

  const visited = new Set();

Các visited biến sẽ theo dõi tất cả các trạng thái đã truy cập giống như tên gọi.

Bây giờ, chúng tôi bắt đầu tìm kiếm thích hợp bằng cách điều hướng qua biểu đồ bắt đầu từ departureState. Nhập mã dưới đây:

while (queue.length > 0) {
    
}

Vòng lặp này sẽ chạy miễn là queue không có sản phẩm nào. Điều đó có nghĩa là miễn là vẫn còn những trạng thái chưa được truy cập.

Gỡ bỏ departureState từ queue trước khi truy cập nó để ngăn mã chạy vào một vòng lặp vô hạn. Sử dụng mã dưới đây:

    const state = queue.shift();

Đoạn mã trên loại bỏ từng state từ phía trước hoặc trên cùng của queue mảng vì hàng đợi sử dụng nguyên tắc Nhập trước xuất trước. Theo mặc định, một mảng sẽ chèn các mục từ phía sau hoặc phía dưới.

Lấy các cạnh (destinations) được kết nối với nút này (state):

    const destinations = connections.get(state);

Bây giờ chúng tôi có quyền truy cập vào trẻ em (destinations) của nút hiện tại (state), hãy kiểm tra xem có cái nào trong số chúng là destinationState.

Vòng lặp qua destinations sử dụng mã này:

for (const destination of destinations) {
    
}

Tại mỗi điểm trong vòng lặp này, hãy kiểm tra xem destinationdestinationState. Nếu nó là trueghi một tin nhắn vào bảng điều khiển:

      if (destination === destinationState) {
          console.log("Found => " + destination);
      }

Sau đó, thêm destination đến visitedqueue mảng nếu nó không có trong visited đã sẵn sàng:

      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination);
      }

Chương trình kết thúc khi tất cả các trạng thái nằm trong visited mảng vì sẽ không có trạng thái để thêm vào queue.

Các bfs chức năng bây giờ trông như thế này:

function bfs(departureState, destinationState) {
  const queue = [departureState];
  const visited = new Set();

  while (queue.length > 0) {
    const state = queue.shift();
    const destinations = connections.get(state);

    for (const destination of destinations) {
      if (destination === destinationState) {
          console.log("Found => " + destination);
      }

      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination);
      }
    }
  }
}

Để kiểm tra xem có kết nối giữa hai (2) trạng thái hay không, giả sử ENUGU và SOKOTO, hãy gọi bfs chức năng như thế này:

bfs("ENUGU", "SOKOTO")

Dưới đây là đầu ra:

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}
Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}
Found => SOKOTO
Found => SOKOTO

Nếu những gì chúng ta đã làm cho đến nay vẫn chưa rõ ràng, tôi khuyên bạn nên chia nhỏ mã ở các điểm khác nhau để bạn có thể thấy chương trình diễn ra như thế nào.

Thuật toán DFS nhận một nút con tại một thời điểm. Nó tiếp tục tìm kiếm một đứa trẻ tại một thời điểm của nút đó cho đến khi nó đi vào ngõ cụt trước khi quay lại và thử một đứa trẻ khác.

Đọc thêm  Giới thiệu về HTML5 Canvas và các hàm JavaScript

Trong trường hợp của chúng tôi, giả sử chúng tôi muốn kiểm tra xem có thể có kết nối nào giữa ENUGU và ABIA hay không.

DFS sẽ bắt đầu từ Enugu và kiểm tra trạng thái đầu tiên được kết nối với nó (LAGOS). Vì LAGOS không phải là ABIA nên tìm kiếm sẽ kiểm tra trạng thái đầu tiên gắn với LAGOS tiếp theo. Nó sẽ tiếp tục cho đến khi tìm thấy ABIA hoặc gặp ngõ cụt. Sau đó, nó sẽ quay lại để kiểm tra một nút khác.

DFS sử dụng ngăn xếp để theo dõi các mục ((các) trạng thái trong trường hợp của chúng tôi) sẽ được truy cập. Khi ngăn xếp trống, quá trình kết thúc. Chúng ta sẽ sử dụng đệ quy để viết mã cho thuật toán DFS. Chúng ta hãy đi đến đó!

Bắt đầu bằng cách tạo một hàm có tên dfs. Nó sẽ nhận ba (3) đối số (departureState, destinationStatevisited):


function dfs(departureState, destinationState, visited = new Set()) {
    
}

Các visited mảng sẽ giữ các trạng thái đã truy cập để tránh vòng lặp vô hạn. Vì vậy, điều đầu tiên được thực hiện trong dfs chức năng là thêm departureState vào visited mảng. Nhập mã này:

  visited.add(departureState);

Tiếp theo, lấy destinations sau đó departureState:

  const destinations = connections.get(departureState);

Bây giờ chúng ta có destinations sau đó departureState, chúng tôi muốn khoanh tròn qua chúng. Nhập mã dưới đây:

  for (let destination of destinations) {
      
  }

Bên trong vòng lặp, kiểm tra xem hiện tại destinationdestinationState. Nếu nó là true, hiển thị thông báo trong bảng điều khiển. Sử dụng mã dưới đây:

    if (destination === destinationState) {
      console.log("Found => " + destination);
    }

Tiếp theo, nếu hiện tại destination vẫn chưa được truy cập, hãy gọi dfs chức năng một lần nữa (đệ quy) – nhưng lần này, sử dụng destination như departureState:

    if (!visited.has(destination)) {
      dfs(destination, destinationState, visited)
    }

Các destinationState không đổi trong khi visited Set() không còn trống nữa. Tại thời điểm này, những đích trong vòng lặp chưa có trong mảng đã truy cập sẽ đi vào ngăn xếp.

Sau đây là những gì dfs chức năng trông giống như:


function dfs(departureState, destinationState, visited = new Set()) {
  
  visited.add(departureState);
  
  const destinations = connections.get(departureState);

  for (let destination of destinations) {
    if (destination === destinationState) {
      console.log("Found => " + destination);
    }

    if (!visited.has(destination)) {
      dfs(destination, destinationState, visited)
    }
  }
}

Để kiểm tra xem có kết nối giữa hai (2) trạng thái hay không, giả sử ENUGU và SOKOTO, hãy gọi dfs chức năng như thế này:

dfs("ENUGU", "SOKOTO")

Xem đầu ra dưới đây:

Map(11) {
  'ENUGU' => [],
  'ABIA' => [],
  'SOKOTO' => [],
  'NIGER' => [],
  'LAGOS' => [],
  'OGUN' => [],
  'BAYELSA' => [],
  'AKWAIBOM' => [],
  'ANAMBRA' => [],
  'IMO' => [],
  'EBONYI' => []
}
Map(11) {
  'ENUGU' => [ 'LAGOS', 'NIGER' ],
  'ABIA' => [ 'OGUN', 'EBONYI' ],
  'SOKOTO' => [ 'NIGER', 'ANAMBRA' ],
  'NIGER' => [ 'ENUGU', 'SOKOTO', 'ANAMBRA' ],
  'LAGOS' => [ 'ENUGU', 'OGUN' ],
  'OGUN' => [ 'LAGOS', 'ABIA', 'EBONYI', 'BAYELSA' ],
  'BAYELSA' => [ 'OGUN' ],
  'AKWAIBOM' => [],
  'ANAMBRA' => [ 'NIGER', 'SOKOTO' ],
  'IMO' => [],
  'EBONYI' => [ 'OGUN', 'ABIA' ]
}
Found => SOKOTO
Found => SOKOTO

Mặc dù đầu ra ở trên giống với kết quả chúng ta nhận được khi chạy hàm bfs, nhưng quá trình để đạt được kết quả này lại khác. Hãy thử chia nhỏ mã tại các điểm khác nhau để xem quy trình của chương trình.

Phần kết luận

Cấu trúc dữ liệu và thuật toán đã trở thành một phần quan trọng trong các cuộc phỏng vấn kỹ thuật phần mềm. Các map() method là một công cụ mạnh mẽ trong JavaScript giúp giải quyết các tác vụ phức tạp như chúng ta đã thấy trong hướng dẫn này dễ dàng hơn.

Chúng tôi bắt đầu bằng cách tạo một biểu đồ bằng cách sử dụng map() phương pháp. Sau đó, chúng tôi đã tìm kiếm các kết nối giữa các trạng thái bằng thuật toán BFS và DFS.

Bạn có thể tìm thấy mã của tôi ở đây

Nó có thể cảm thấy hơi choáng ngợp nếu bạn chưa quen với các thuật toán và cấu trúc dữ liệu. Nhưng với thực hành lặp đi lặp lại, bạn sẽ quen với nó. Vì vậy, nếu ban đầu bạn cảm thấy khó hiểu chuyện gì đang xảy ra, hãy nghỉ ngơi và quay lại với nó với một cái đầu minh mẫn hơn.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status