Task4/main.py - master - timshk/Shalaev_Stepik

Task4/main.py
133 строки5 KB
timshk
Stepik задания
01 июн 2026, 18:58
01 июн 2026, 18:582e75834
"""
Гибридная квантовая оптимизация для задачи Max-Cut
(распределение грузов по машинам на основе несовместимости)
"""

import numpy as np
from data.example_data import get_incompatibility_matrix, get_weights, get_capacity
from src.qaoa import (
    build_maxcut_hamiltonian, run_qaoa, get_distribution
)
from src.visualization import plot_graph, plot_results_table


def decode_solution(bits_str, n_nodes):
    """Преобразует битовую строку в список назначений."""
    bits_str = bits_str.zfill(n_nodes)
    return [int(b) for b in bits_str[:n_nodes]]


def compute_cut_value(solution, incompatibility_matrix):
    """Вычисляет вес разреза для данного решения."""
    n = len(solution)
    cut = 0
    for i in range(n):
        for j in range(i+1, n):
            if solution[i] != solution[j]:
                cut += incompatibility_matrix[i][j]
    return cut


def brute_force_optimal(incompatibility_matrix):
    """Находит оптимальное решение полным перебором."""
    n = len(incompatibility_matrix)
    best_cut = -1
    best_solution = None
    
    for bits in range(2**n):
        solution = [(bits >> i) & 1 for i in range(n)]
        cut = compute_cut_value(solution, incompatibility_matrix)
        if cut > best_cut:
            best_cut = cut
            best_solution = solution
    
    return best_solution, best_cut


def main():
    print("="*60)
    print("ГИБРИДНАЯ ОПТИМИЗАЦИЯ ЗАГРУЗКИ ТРАНСПОРТА")
    print("="*60)
    
    # Загрузка данных
    incompatibility = get_incompatibility_matrix()
    weights = get_weights()
    capacity = get_capacity()
    n_nodes = len(incompatibility)
    
    print(f"\nГрузов: {n_nodes}")
    print(f"Матрица несовместимости:\n{incompatibility}")
    
    # Визуализация исходного графа
    plot_graph(incompatibility, title="Исходный граф несовместимости")
    
    # Построение гамильтониана
    hamiltonian_terms = build_maxcut_hamiltonian(incompatibility)
    print(f"\nГамильтониан: {len(hamiltonian_terms)} термов Z_i Z_j")
    
    # Запуск QAOA
    result = run_qaoa(hamiltonian_terms, n_nodes, n_layers=2, maxiter=50)
    
    # Получение распределения решений
    counts = get_distribution(result['gammas'], result['betas'], 
                              hamiltonian_terms, n_nodes, shots=4096)
    
    # Находим лучшее решение из измерений
    best_solution = None
    best_cut = -1
    
    print("\nТоп-5 решений:")
    total_shots = sum(counts.values())
    sorted_items = sorted(counts.items(), key=lambda x: -x[1])
    
    for bits_str, count in sorted_items[:5]:
        solution = decode_solution(bits_str, n_nodes)
        cut = compute_cut_value(solution, incompatibility)
        prob = count / total_shots
        print(f"  {solution} -> вес разреза = {cut}, вероятность = {prob:.3f}")
        if cut > best_cut:
            best_cut = cut
            best_solution = solution
    
    # Сравнение с brute-force
    optimal_solution, optimal_cut = brute_force_optimal(incompatibility)
    
    print(f"\nЛучшее решение QAOA: {best_solution} (вес = {best_cut})")
    print(f"Оптимальное решение: {optimal_solution} (вес = {optimal_cut})")
    
    if best_cut == optimal_cut:
        print("\n✅ QAOA достиг глобального оптимума!")
    else:
        print(f"\n⚠️ QAOA не достиг оптимума (отрыв {optimal_cut - best_cut})")
    
    # Формирование назначений для вывода
    assignments = {
        "A": [f"Груз {i+1}" for i, bit in enumerate(best_solution) if bit == 0],
        "B": [f"Груз {i+1}" for i, bit in enumerate(best_solution) if bit == 1]
    }
    
    # Визуализация результата
    plot_graph(incompatibility, solution=best_solution, title="Найденное решение")
    
    print("\n" + "="*50)
    print("ПЛАН ЗАГРУЗКИ")
    print("="*50)
    for truck, cargo in assignments.items():
        print(f"Машина {truck}: {cargo}")
    
    # Дополнительно: проверка весов
    print("\n" + "="*50)
    print("ПРОВЕРКА ОГРАНИЧЕНИЙ")
    print("="*50)
    for truck, cargo in assignments.items():
        total_weight = sum(weights[int(c.split()[1])-1] for c in cargo)
        status = "✅" if total_weight <= capacity else "❌ ПЕРЕГРУЗ!"
        print(f"Машина {truck}: вес {total_weight}кг, лимит {capacity}кг {status}")
    
    # Эффективность
    efficiency = (best_cut / optimal_cut) * 100 if optimal_cut > 0 else 0
    print(f"\nЭффективность решения: {efficiency:.1f}%")


if __name__ == "__main__":
    main()