close

Giải thuật Tìm kiếm theo Heuristics trong C++ - Giải thích, Ví dụ và Mã nguồn

Tìm kiếm theo Heuristics là một phương pháp thuật toán mạnh mẽ được sử dụng để tìm các giải pháp trong không gian vấn đề phức tạp bằng cách đưa ra các quyết định thông minh dựa trên các heuristics hoặc quy tắc kinh nghiệm. Điều này đặc biệt hữu ích khi việc tìm kiếm toàn diện trở nên không khả thi do không gian tìm kiếm lớn.

Cách hoạt động

  1. Đánh giá Heuristics: Thuật toán đánh giá mỗi trạng thái trong không gian vấn đề bằng cách sử dụng hàm heuristics. Hàm này ước tính mức độ "hứa hẹn" của mỗi trạng thái dựa trên mức tiến gần đến trạng thái mục tiêu.
  2. Chiến lược Tìm kiếm: Thuật toán chọn trạng thái có triển vọng nhất dựa trên đánh giá heuristics. Nó sử dụng một chiến lược tìm kiếm như Tìm kiếm Best-First, Tìm kiếm A*, hoặc Tìm kiếm Greedy.
  3. Mở rộng Trạng thái: Trạng thái được chọn được mở rộng bằng cách tạo ra các trạng thái hàng xóm của nó. Đây là các ứng viên tiềm năng cho bước tiếp theo.
  4. Lặp lại: Quá trình được lặp lại theo từng bước, lựa chọn và mở rộng các trạng thái cho đến khi tìm thấy trạng thái mục tiêu hoặc đáp ứng điều kiện kết thúc.

Ví dụ: Bài toán Người du lịch (TSP)

Xem xét bài toán Người du lịch, trong đó một người du lịch cần thăm một tập các thành phố và quay trở lại thành phố xuất phát sao cho quãng đường tổng cực tiểu. Một phương pháp tiếp cận heuristics có thể là thuật toán Người hàng xóm Gần nhất:

  1. Bắt đầu tại một thành phố bất kỳ.
  2. Tại mỗi bước, chọn thành phố chưa được thăm gần nhất làm điểm đến tiếp theo.
  3. Lặp lại cho đến khi tất cả các thành phố được thăm qua, sau đó quay trở lại thành phố xuất phát.

Mã nguồn ví dụ trong C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

struct City {
    int x, y;
};

double distance(const City& city1, const City& city2) {
    return std::sqrt(std::pow(city1.x - city2.x, 2) + std::pow(city1.y - city2.y, 2));
}

std::vector<int> nearestNeighbor(const std::vector<City>& cities) {
    int numCities = cities.size();
    std::vector<int> path(numCities);
    std::vector<bool> visited(numCities, false);

    path[0] = 0;
    visited[0] = true;

    for (int i = 1; i < numCities; ++i) {
        int currentCity = path[i - 1];
        double minDist = std::numeric_limits<double>::max();
        int nextCity = -1;

        for (int j = 0; j < numCities; ++j) {
            if (!visited[j]) {
                double dist = distance(cities[currentCity], cities[j]);
                if (dist < minDist) {
                    minDist = dist;
                    nextCity = j;
                }
            }
        }

        path[i] = nextCity;
        visited[nextCity] = true;
    }

    path.push_back(0); // Quay trở lại thành phố xuất phát
    return path;
}

int main() {
    std::vector<City> cities = {{0, 0}, {1, 3}, {4, 2}, {3, 6}, {7, 1}};
    std::vector<int> path = nearestNeighbor(cities);

    std::cout << "Đường đi của Người du lịch: ";
    for (int city

Trong ví dụ này, Thuật toán láng giềng gần nhất được sử dụng để giải bài toán Người bán hàng du lịch. Đó là một cách tiếp cận heuristic chọn thành phố chưa được ghé thăm gần nhất ở mỗi bước, dẫn đến một giải pháp thường gần với mức tối ưu.