Search
Search

Solving a complex recurrence relation for the Traveling Salesman

drewying Published at Dev
16
drewying

I need to solve the exact time complexity for the brute force version of the Traveling Salesman using a recurrence relation.

I've worked out the recurrence relation to be as follows: T(n)=T(n-1)*(n-1)+1

But I'm having trouble reducing that that to a closed form of the function, and thus get the exact time complexity. Not for lack of trying either. It's looking like it's coming out as a binomial sequence but my algebra is a bit rusty.

If anyone could help or point me on the right path I would appreciate it.

Thanks!

vib

Here are a few hints :

  • define R(n) = T(n)/(n-1)!
  • solve the recurrence for R(n)
  • express T(n) as a function of R(n)

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Recurrence relation: iteration solving

From Dev

Outsmarting a Traveling Salesman Algorithm

From Dev

Traveling Salesman for java

From Dev

Traveling Salesman (TSP) no return

From Dev

Traveling Salesman assignment

From Dev

How is the branch and bound algorithm faster than the brute force algorithm when solving the Traveling Salesman Problem?

From Dev

Traveling salesman including traveling through cities

From Dev

Possible "Traveling Salesman" function in Matlab?

From Dev

Python Traveling Salesman Greedy Algorithm

From Dev

Recurrence Relation: Writing a recurrence relation

From Dev

finding the optimum solution of a scene similar to traveling salesman

From Java

Traveling Salesman problem without restriction on the number of visits

From Dev

A local search heuristic for a subtour in an asynchronous traveling salesman

From Dev

Traveling Salesman: Get all possible Paths with recursion

From Dev

Using circular permutations to reduce Traveling Salesman complexity

From Dev

Traveling salesman (TSP) for line routes, snowplowing

From Dev

Neo4J - Traveling Salesman

From Dev

Traveling Salesman - 2-Opt improvement

From Dev

Java, genetic algorithm traveling salesman issue

From Dev

A local search heuristic for a subtour in an asynchronous traveling salesman

From Dev

Traveling Salesman: Get all possible Paths with recursion

From Dev

MATLAB plot the solution for the Traveling Salesman Problem

From Dev

Solving a Recurrence Relation: T(n)=T(n-1)+T(n/2)+n

From Dev

Solving Recurrence relation: T(n) = 3T(n/5) + lgn * lgn

From Dev

Solving non-homogeneous linear recurrence relation in O(log n) time

From Dev

Solving Recurrence relation: T(n) = 3T(n/5) + lgn * lgn

From Dev

Solving recurrence equation by substituion

From Dev

Solving recurrence equations

From Dev

Java recurrence relation with for loop

Related Related

  1. 1

    Recurrence relation: iteration solving

  2. 2

    Outsmarting a Traveling Salesman Algorithm

  3. 3

    Traveling Salesman for java

  4. 4

    Traveling Salesman (TSP) no return

  5. 5

    Traveling Salesman assignment

  6. 6

    How is the branch and bound algorithm faster than the brute force algorithm when solving the Traveling Salesman Problem?

  7. 7

    Traveling salesman including traveling through cities

  8. 8

    Possible "Traveling Salesman" function in Matlab?

  9. 9

    Python Traveling Salesman Greedy Algorithm

  10. 10

    Recurrence Relation: Writing a recurrence relation

  11. 11

    finding the optimum solution of a scene similar to traveling salesman

  12. 12

    Traveling Salesman problem without restriction on the number of visits

  13. 13

    A local search heuristic for a subtour in an asynchronous traveling salesman

  14. 14

    Traveling Salesman: Get all possible Paths with recursion

  15. 15

    Using circular permutations to reduce Traveling Salesman complexity

  16. 16

    Traveling salesman (TSP) for line routes, snowplowing

  17. 17

    Neo4J - Traveling Salesman

  18. 18

    Traveling Salesman - 2-Opt improvement

  19. 19

    Java, genetic algorithm traveling salesman issue

  20. 20

    A local search heuristic for a subtour in an asynchronous traveling salesman

  21. 21

    Traveling Salesman: Get all possible Paths with recursion

  22. 22

    MATLAB plot the solution for the Traveling Salesman Problem

  23. 23

    Solving a Recurrence Relation: T(n)=T(n-1)+T(n/2)+n

  24. 24

    Solving Recurrence relation: T(n) = 3T(n/5) + lgn * lgn

  25. 25

    Solving non-homogeneous linear recurrence relation in O(log n) time

  26. 26

    Solving Recurrence relation: T(n) = 3T(n/5) + lgn * lgn

  27. 27

    Solving recurrence equation by substituion

  28. 28

    Solving recurrence equations

  29. 29

    Java recurrence relation with for loop

HotTag

Archive