2 ms·

I didn't ask it to use BFS, I asked it to write a program that would come up with the shortest path in a graph. It decided to use BFS on its own. I agree that B

• cercatrova 4y ago
  Can you ask it for something more complicated like the traveling salesman implementation (which is NP hard yes but more efficient algorithms exist)? It gave me a genetic algorithm: // Define a class for representing a single city in the TSP class City { constructor(public x: number, public y: number) {} // Calculate the distance to another city public distanceTo(city: City): number { const dx = this.x - city.x; const dy = this.y - city.y; return Math.sqrt(dx * dx + dy * dy); } } // Define a class for representing a solution to the TSP class Tour { private cities: City[]; private fitness = 0; private distance = 0; constructor(tour?: City[]) { if (tour) { this.cities = tour; } else { this.cities = []; } } // Add a city to the tour public addCity(city: City) { this.cities.push(city); } // Get the tour as an array of cities public getTour(): City[] { return this.cities; } // Get the fitness of the tour (lower is better) public getFitness(): number { if (this.fitness === 0) { this.fitness = 1 / this.getDistance(); } return this.fitness; } // Get the total distance of the tour public getDistance(): number { if (this.distance === 0) { let tourDistance = 0; // Loop through all cities in the tour and sum the distances for (let i = 0; i < this.cities.length; i++) { const fromCity = this.cities[i]; const toCity = this.cities[0]; if (i + 1 < this.cities.length) { toCity = this.cities[i + 1]; } tourDistance += fromCity.distanceTo(toCity); } this.distance = tourDistance; } return this.distance; } // Generate a random tour public generateIndividual(): Tour { const newTour = new Tour(); for (let i = 0; i < Tour.numberOfCities(); i++) { newTour.addCity(Tour.getCity(i)); } return newTour.shuffle(); } // Shuffle the cities in the tour public shuffle(): Tour { const newTour = new Tour(this.cities); const currentIndex = newTour.cities.length; let temporaryValue; let randomIndex; // While there remain elements to shuffle... while (currentIndex !== 0) { // Pick a remaining element... randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // And swap it with the current element temporaryValue = newTour.cities[currentIndex]; newTour.cities[currentIndex] = newTour.cities[randomIndex]; newTour.cities[randomIndex] = temporaryValue; } return ... It stopped here and continued when I asked it to but I stopped here because I don't want to exceed the HN limit.