Hej, mam pewne zadanie do wykonania i bardzo mało czasu.
Przy użyciu C# mam napisać program wytyczający trasę mając do wykorzystania pewien zbiór obiektów (miasto1, miasto2, odległość między nimi)
Widziałem już kilka przykładów i omówień z Javy i C/C++ ale potrzebował bym pomocy przy utworzeniu takiej małej aplikacji konsolowej gdzie podając dwa miasta program wybierze najkrótszą trasę i poda kolejne mijane miejscowości + ostateczną odległość
Ale w ogóle rozumiesz, jak to ma działać? Jak działa algorytm?
Czy umiałbyś to zrobić na kartce, albo komuś wytłumaczyć kroki, jakie trzeba zrobić, żeby zadanie rozwiązać?
Na razie, poza opisem zadania, nie dałeś niczego. Także nie wiem, czy potrzebujesz pomocy (wtedy napisz konkretnie, gdzie utknąłeś), czy czekasz, aż ktoś to zrobi za Ciebie?
Aktualnie mam utworzoną klasę z trasami. Co do wiedzy, to wydaje mi się ;) że umiałbym rozrysować komuś na kartce takie zagadnienie.
Trochę spanikowałem bo będę robił bardziej zawansowany algorytm.
Ewentualnie możesz skorzystać z Chat GPT. Zrobiłem to za Ciebie i oto odpowiedź :P
Witaj! Zadanie, które opisujesz, to problem najkrótszej ścieżki w grafie, który można rozwiązać za pomocą algorytmów takich jak Dijkstra, Bellmana-Forda lub A*. Oto kilka kroków, które pomogą Ci napisać program, który rozwiąże ten problem w C#:
Miasto, która będzie reprezentować każde miasto. Klasa powinna zawierać pola nazwa i sąsiedzi, które będą przechowywać informacje o nazwie miasta i o innych miastach, do których prowadzą bezpośrednie połączenia oraz ich odległości.public class Miasto
{
public string Nazwa { get; set; }
public Dictionary<Miasto, int> Sąsiedzi { get; set; }
public Miasto(string nazwa)
{
Nazwa = nazwa;
Sąsiedzi = new Dictionary<Miasto, int>();
}
}
Graf, która będzie reprezentować zbiór miast i połączeń między nimi. Klasa powinna zawierać pole miasta, które będzie przechowywać informacje o wszystkich miastach w grafie.public class Graf
{
public List<Miasto> Miasta { get; set; }
public Graf()
{
Miasta = new List<Miasto>();
}
public void DodajMiasto(Miasto miasto)
{
Miasta.Add(miasto);
}
}
Graf, które umożliwią dodanie połączeń między miastami. Metoda DodajPołączenie będzie dodawać połączenie między dwoma miastami o podanych nazwach i odległości.public void DodajPołączenie(string nazwaMiasta1, string nazwaMiasta2, int odległość)
{
var miasto1 = Miasta.Find(m => m.Nazwa == nazwaMiasta1);
var miasto2 = Miasta.Find(m => m.Nazwa == nazwaMiasta2);
miasto1.Sąsiedzi.Add(miasto2, odległość);
miasto2.Sąsiedzi.Add(miasto1, odległość);
}
NajkrótszaŚcieżka, która za pomocą algorytmu Dijkstry wyznaczy najkrótszą ścieżkę między dwoma miastami. Metoda powinna przyjmować nazwy miast jako argumenty oraz zwracać listę miast, które należy odwiedzić, aby dotrzeć z pierwszego miasta do drugiego, oraz długość tej trasy.public (List<Miasto> Ścieżka, int Długość) NajkrótszaŚcieżka(string nazwaMiasta1, string nazwaMiasta2)
{
var start = Miasta.Find(m => m.Nazwa == nazwaMiasta1);
var meta = Miasta.Find(m => m.Nazwa ==
Masz na zachętę:
https://dotnetfiddle.net/csInsp
Program rozwiązuje problem komiwojażera, ale bardzo niewydajnie. Sprawdza on po kolei wszystkie połączenia między punktem A a B i tak do czasu, aż znajdzie szukany punkt.
Wkleję efekt końcowy. Może się komuś przyda.
Wydaje się, że wyszło całkiem przyzwoicie.
using Komiwojażer;
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
static void Main(string[] args)
{
Graf graf = new Graf();
odleglosci trasy = new odleglosci();
// utwórz obiekt Miasto i dodaj go do klasy Graf wszystkie połączenia(sąsiadów).
foreach (var trasa in trasy.GetTrasy())
{
Miasto miasto1 = new Miasto(trasa.miejscowosc1);
Miasto miasto2 = new Miasto(trasa.miejscowosc2);
if (!graf.Miasta.Contains(miasto1))
graf.DodajMiasto(miasto1);
else
miasto1 = graf.Miasta.Find(m => m.Nazwa == trasa.miejscowosc1);
if (!graf.Miasta.Contains(miasto2))
graf.DodajMiasto(miasto2);
else
miasto2 = graf.Miasta.Find(m => m.Nazwa == trasa.miejscowosc2);
graf.DodajPołączenie(trasa.miejscowosc1, trasa.miejscowosc2, (double)trasa.odleglosc);
}
// znajdź najkrótszą trasę pomiędzy dwoma miastami.
//toDo
//dla użytkownika należy wyświetlić wszystkie miasta i ma mieć możliwość wybrania najkrótszej
var (ścieżka, długość) = graf.NajkrótszaŚcieżka("Miasto1", "Miasto2");
// podaj resultat
Console.WriteLine("Najkrótsza ścieżka:");
int i = 1;
foreach (var miasto in ścieżka)
{
if (i != ścieżka.Count())
{
i++;
miasto.Nazwa += " -> ";
}
Console.Write(miasto.Nazwa);
}
Console.WriteLine($"\nRAZEM: {długość}");
}
}
public class Miasto : IComparable<Miasto>
{
public string Nazwa { get; set; }
public Dictionary<Miasto, double> Sąsiedzi { get; set; }
public Miasto(string nazwa)
{
Nazwa = nazwa;
Sąsiedzi = new Dictionary<Miasto, double>();
}
//nieuzywany fragment ale wymaga tego zaimplementowany interfejs
public int CompareTo(Miasto other)
{
return Nazwa.CompareTo(other.Nazwa);
}
}
public class Graf
{
public List<Miasto> Miasta { get; set; }
public Graf()
{
Miasta = new List<Miasto>();
}
public void DodajMiasto(Miasto miasto)
{
Miasta.Add(miasto);
}
public void DodajPołączenie(string nazwaMiasta1, string nazwaMiasta2, double odległość)
{
var miasto1 = Miasta.Find(m => m.Nazwa == nazwaMiasta1);
var miasto2 = Miasta.Find(m => m.Nazwa == nazwaMiasta2);
miasto1.Sąsiedzi.Add(miasto2, odległość);
miasto2.Sąsiedzi.Add(miasto1, odległość);
}
public (List<Miasto> Ścieżka, double Długość) NajkrótszaŚcieżka(string nazwaMiasta1, string nazwaMiasta2)
{
//określenie miejsca startu i końca trasy
var start = Miasta.Find(m => m.Nazwa == nazwaMiasta1);
var meta = Miasta.Find(m => m.Nazwa == nazwaMiasta2);
var odległości = new SortedDictionary<Miasto, double>(Comparer<Miasto>.Create((x, y) => x.Nazwa.CompareTo(y.Nazwa)));
var poprzednicy = new Dictionary<Miasto, Miasto>();
var kolejka = new SortedSet<(double, Miasto)>();
foreach (var _miasto in Miasta)
{
odległości[_miasto] = double.PositiveInfinity;
}
odległości[start] = 0;
kolejka.Add((0, start));
while (kolejka.Count > 0)
{
var (obecnaOdległość, obecneMiasto) = kolejka.Min;
kolejka.Remove((obecnaOdległość, obecneMiasto));
if (obecneMiasto == meta)
{
break;
}
foreach (var (sąsiad, odległość) in obecneMiasto.Sąsiedzi)
{
var alternatywnaOdległość = odległości[obecneMiasto] + odległość;
if (alternatywnaOdległość < odległości[sąsiad])
{
odległości[sąsiad] = alternatywnaOdległość;
poprzednicy[sąsiad] = obecneMiasto;
kolejka.Add((alternatywnaOdległość, sąsiad));
}
}
}
var ścieżka = new List<Miasto>();
var miasto = meta;
while (miasto != start)
{
ścieżka.Add(miasto);
miasto = poprzednicy[miasto];
}
ścieżka.Add(start);
ścieżka.Reverse();
return (ścieżka, odległości[meta]);
}
}
P.s.
Polskie nazwy w kodzie i komentarze są celowe. (choć wiem, że tak nie robi się, ale na potrzeby instruktarzowe chciałem to tak przedstawić.)
cerrato napisał(a):
Ewentualnie możesz skorzystać z Chat GPT. Zrobiłem to za Ciebie i oto odpowiedź :P
Witaj! Zadanie, które opisujesz, to problem najkrótszej ścieżki w grafie, który można rozwiązać za pomocą algorytmów takich jak Dijkstra, Bellmana-Forda lub A*. Oto kilka kroków, które pomogą Ci napisać program, który rozwiąże ten problem w C#:
Przeciez ten problem polega na znalezieniu cyklu Hamiltona. I ogolnie to jest NP. Co on bredzi o jakichs Djikstrach czy A*? :P
EDIT:
ale potrzebował bym pomocy przy utworzeniu takiej małej aplikacji konsolowej gdzie podając dwa miasta program wybierze najkrótszą trasę i poda kolejne mijane miejscowości + ostateczną odległość
Dobra. To jednak OP zle opisal (w temacie) co potrzebuje. Heh. :D
Autor prawdopodobnie nadal nie wie jak rozwiązać problem (bez urazy) ale go rozwiązał :)
Co jest bardziej potrzebne w życiu / pracy, umiejętność rozwiązania tego problemu czy dostarczenie rozwiązania ? Ja po kilku latach pracy mogę odpowiedzieć za siebie że to drugie.