การวางเส้นทาง

ตัวอย่างที่ 1 ค้นทุกทางเทียบวิธีเลือกจุดใกล้สุด

พิกัดสมมติเป็นกิโลเมตร H คือโรงพยาบาล

import math
from itertools import permutations

SITES = {"H": (0, 0), "A": (1.0, 2.5), "B": (1.5, 0.0), "C": (-2.0, 1.0), "D": (4.0, 0.5)}

def length(order):
    stops = ["H", *order, "H"]
    return sum(math.dist(SITES[a], SITES[b]) for a, b in zip(stops, stops[1:]))

best = min(permutations("ABCD"), key=length)

current, left, greedy = "H", set("ABCD"), []
while left:
    nxt = min(sorted(left), key=lambda s: math.dist(SITES[current], SITES[s]))
    greedy.append(nxt)
    left.remove(nxt)
    current = nxt

print(f"exhaustive: H-{'-'.join(best)}-H = {length(best):.2f} km")
print(f"nearest neighbour: H-{'-'.join(greedy)}-H = {length(greedy):.2f} km "
      f"(+{length(greedy) / length(best) - 1:.0%})")

exhaustive: H-B-D-A-C-H = 13.25 km
nearest neighbour: H-B-A-C-D-H = 17.46 km (+32%)

วิธีเลือกจุดใกล้สุดเริ่มดีที่ B แต่ไปติดที่ C ทางซ้าย แล้วต้องบินข้ามไป D ทางขวาไกล ทำให้ยาวกว่าคำตอบที่ดีที่สุดราวหนึ่งในสาม ฮิวริสติกจึงต้องตรวจคุณภาพเทียบคำตอบที่ดีกว่าเสมอเมื่อทำได้

ตัวอย่างที่ 2 ตรวจพลังงานและแบ่งเป็นสองเที่ยว

สมมติใช้พลังงาน 33.3 Wh/km เมื่อบรรทุก 2 kg แบตเตอรี่ 500 Wh ใช้ได้ 80% สำรอง 20%

import math
from itertools import combinations, permutations

SITES = {"H": (0, 0), "A": (1.0, 2.5), "B": (1.5, 0.0), "C": (-2.0, 1.0), "D": (4.0, 0.5)}
WH_PER_KM, BATTERY_WH, USABLE, RESERVE = 33.3, 500, 0.8, 0.2
available = BATTERY_WH * USABLE * (1 - RESERVE)

def best_trip(stops):
    def km(order):
        path = ["H", *order, "H"]
        return sum(math.dist(SITES[a], SITES[b]) for a, b in zip(path, path[1:]))
    order = min(permutations(stops), key=km)
    return order, km(order)

order, km = best_trip("ABCD")
print(f"available {available:.0f} Wh; one trip {km:.2f} km needs {km * WH_PER_KM:.0f} Wh "
      f"-> {'OK' if km * WH_PER_KM <= available else 'NOT feasible'}")

plans = []
for pair in combinations("ABCD", 2):
    other = "".join(s for s in "ABCD" if s not in pair)
    trips = [best_trip(pair), best_trip(other)]
    if all(k * WH_PER_KM <= available for _, k in trips):
        plans.append((sum(k for _, k in trips), trips))
total, trips = min(plans)
for o, k in trips:
    print(f"trip H-{'-'.join(o)}-H: {k:.2f} km, {k * WH_PER_KM:.0f} Wh")
print(f"two trips total {total:.2f} km")

available 320 Wh; one trip 13.25 km needs 441 Wh -> NOT feasible
trip H-A-C-H: 8.28 km, 276 Wh
trip H-B-D-H: 8.08 km, 269 Wh
two trips total 16.36 km

เที่ยวเดียวครบสี่จุดต้องใช้พลังงานเกินที่ใช้ได้ จึงแบ่งเป็นสองเที่ยว คู่ที่ดีที่สุดคือ B กับ D และ A กับ C ระยะรวมมากกว่าเที่ยวเดียวราว 23% แต่ทุกเที่ยวมีสำรองครบ ถ้าลมต้านแรง พลังงานต่อกิโลเมตรเพิ่มขึ้น ต้องคำนวณใหม่ก่อนบินทุกครั้ง