home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

เส้นทางสั้นที่สุดเยี่ยมชมทุกโหนดใน C++

คำอธิบายปัญหา

กราฟไม่มีทิศทาง เชื่อมต่อ N โหนด หาความยาวเส้นทางสั้นที่สุดที่เยี่ยมชมทุกโหนด (เริ่ม/จบที่ไหนก็ได้, เยี่ยมซ้ำ/ใช้ edge ซ้ำได้)

ตัวอย่าง

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] → Output: 4
Path: [0,1,4,2,3]

แนวทางแก้ปัญหา: BFS + Bitmask State

State: (mask, node) โดย mask = bitmask ของโหนดที่เยี่ยมแล้ว

BFS:

  • เริ่มจากทุกโหนด: (1<
  • เป้าหมาย: mask == (1<
  • Transition: จาก (mask, u) ไป (mask | (1<
  • Visited: visited[u][mask] ป้องกันซ้ำ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int target = (1<

ความซับซ้อน

  • เวลา: O(n × 2ⁿ) (n ≤ 12 ในโจทย์ต้นฉบับ)
  • พื้นที่: O(n × 2ⁿ)