TSP Search Algorithms

A C# .NET 8 console application that solves the Traveling Salesman Problem (TSP) using three different graph search algorithms — Depth-First Search, Least-Cost Search, and A* Search — and compares their performance on various graph inputs.

Features

• Solve TSP using three algorithms: DFS, Least-Cost Search, and A*
• Compare algorithm results side-by-side (path, cost, execution time)
• Build graphs manually via adjacency matrices or generate them randomly
• Extensible architecture using interfaces (IGraph, IGraphBuilder, ITSPGraphTraversalAlgorithm)

Prerequisites

• .NET 8 SDK or later

How to Run

Command Line

dotnet run

Visual Studio

1. Open HomeworkAssignmentAI.sln in Visual Studio 2022+
2. Press F5 or click Start

Configuration

The entry point is Program.cs. To change the graph or algorithms being used:

1. Choose a graph builder:

   • ManualMatrixGraphBuilder — provide your own adjacency matrix
   • RandomMatrixGraphBuilder(nodeCount, minWeight, maxWeight) — generate a random graph

2. Choose algorithms by adding them to the dictionary passed to TravelingSalesmanProblem:

   • 1 → Depth-First Search
   • 2 → Least-Cost Search
   • 3 → A* Search

3. Run an algorithm by calling tsp.SelectAlgorithmAndRun(id) with the desired algorithm ID.

Example Output

Algorithm: A* Search
Path:
(0, 1) , (1, 3) , (3, 2) , (2, 0) Cost: 80
Run Time: 11 ms

Project Structure

├── Program.cs                      # Entry point — configures graphs and algorithms
├── TravelingSalesmanProblem.cs      # Orchestrator — runs selected algorithm and displays results
│
├── IGraph.cs                       # Interface for graph representation
├── AdjacencyMatrixGraph.cs         # Adjacency matrix implementation of IGraph
│
├── IGraphBuilder.cs                # Interface for graph construction
├── ManualMatrixGraphBuilder.cs     # Builds a graph from a user-defined matrix
├── RandomMatrixGraphBuilder.cs     # Builds a graph with random edge weights
│
├── ITSPGraphTraversalAlgorithm.cs  # Interface for TSP solving algorithms
├── AStar.cs                        # A* Search implementation
├── DepthFirstSearch.cs             # Depth-First Search implementation
├── LeastCostSearch.cs              # Least-Cost Search implementation
│
├── State.cs                        # Search state used by algorithms
├── IDisplayResults.cs              # Interface for result display
├── DisplayResults.cs               # Console output of algorithm results
│
├── HomeworkAssignmentAI.csproj     # .NET 8 project file
└── HomeworkAssignmentAI.sln        # Visual Studio solution file

License

This project is licensed under the MIT License — see the LICENSE file for details.