Problem Komiwojażera [C++]

problem komiwojażera

Problem komiwojażera

Programistą nigdy nie byłem i prawdopodobnie nigdy nie będę, aczkolwiek kilka programów udało się popełnić – nie twierdzę, że wszystkie samodzielnie ale liczy się fakt rozumienia kodu (tak sobie przynajmniej wmawiam 🙂 ).

Poniższy kod dotyczy Problemu Komiwojażera. Całkiem nieźle radzi sobie z obliczaniem optymalnej trasy. Starałem się umieszczać komentarze wszędzie gdzie to możliwe, więc nie powinieneś mieć problemu ze zrozumieniem jak program działa.

Dla potomności poniżej kod programu:

#include <iostream>
#include <math.h>
#include <iomanip> // potrzebne do precyzji
using namespace std;

int main()
{
//Zmienne
int
miasto_start,
miasto_nr,
sasiad = 0;

//deklaracja tablcy dwuwymiarowej dla wspolrzednych
float droga_calkowita;
float SUM = 0;

cout << „Ilosc miast: „;
cin >> miasto_nr;
float tab[miasto_nr][2];

//wpisanie danch do tablicy
for (int i=0, j=1; i<miasto_nr; i++,j++)
{
cout << „Pozycja x miasta „<< j << ” na osi xy\t”;
cin >> tab[i][0];
cout << „Pozycja y miasta „<< j << ” na osi xy\t”;
cin >> tab[i][1];
cout << „\n”;
}

// wybór miasta startowego
while(miasto_start <= 0 || miasto_start > miasto_nr){
cout << „\nMiasto startowe: „;
cin >> miasto_start;
}

miasto_start –; //dopasowanie do pozyji w tablicy
cout<<„\n\nTrasa wg. algorytmu najblizszego sasiada:\n”;
// stwozenie tablicy dla odwiedzonych miast
bool odwiedzone_tab[miasto_nr];
for(int i=0; i<miasto_nr; i++) odwiedzone_tab[i] = false;
odwiedzone_tab[miasto_start] = true;

cout<<miasto_start+1;

//OBLICZENIA
int temp = miasto_start; // tablica pomocnicza
for(int i=0; i<miasto_nr-1; i++)
{

float miasto_x = tab[temp][0]; //wartość x miasta w którym jestem wyciagnieta z tablicy miast
float miasto_y = tab[temp][1]; //wartość y miasta w którym jestem wyciagnieta z tablicy miast

float dystans=0, najblizsza_odleglosc=0;
bool first = true;

for(int i=0; i<miasto_nr; i++)
{
if(odwiedzone_tab[i] == false)
{
cout<<setprecision(2); // Ustawienie precyzji wyniku
dystans = sqrt(pow((miasto_x – tab[i][0]), 2) + pow((miasto_y – tab[i][1]),2)); //obiczneie odleglosci (x1-x2)^2 + (y1-y2)^2 [pierwiatek z wartosci]
if(first == true)
{
najblizsza_odleglosc = dystans+1;
first = false;
}
if(dystans != 0 && dystans < najblizsza_odleglosc) // sprawdzenie czy odleglosc jest najmniejsza
{
najblizsza_odleglosc = dystans; //przypisanie wartosci dystans do najblizsza_odlegosc
sasiad = i; // numer miast do ktorego odleglosc jest najmniejsza
}
}
}
SUM += najblizsza_odleglosc; // suma odleglosci przebytej drogi
temp = sasiad;
odwiedzone_tab[temp] = true;
cout<<” -> „<<sasiad+1;
}
cout<<” -> „< droga_calkowita = sqrt(pow((tab[miasto_start][0] – tab[sasiad][0]), 2) + pow((tab[miasto_start][1] – tab[sasiad][1]),2)); // powrot do miasta startowego
SUM += droga_calkowita;
cout<<„\n\nCalkowita dlugosc trasy: „<<SUM<<„\n”;
return 0;
}

Jeśli masz problem przy kopiowaniu powyższego kodu – użyj pliku txt, który znajdziesz >> TUTAJ <<

 

 

3 Komentarzy

  1. kealion

    Dlaczego podczas kompilacji (linia 82 – cout< „< droga_calkowita (…)) wyrzuca błąd?

    1. Paweł (Post autora)

      Niestety szklana kula jest w naprawie… 🙂 Jakieś logi błędów ?

  2. Patryk

    niestety też mam problem w linii 81

    |81|error: no match for ‚operator=’ (operand types are ‚std::basic_ostream::__ostream_type {aka std::basic_ostream}’ and ‚double’)|

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *