Question

The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning, there are n garage sales going on, ${\mathbf{g}}_{\mathbf{1}}\mathbf{,}{\mathbf{g}}_{\mathbf{2}}\mathbf{,}{\mathbf{g}}_{\mathbf{3}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{g}}_{\mathbf{n}}$. For each garage sale ${\mathbf{g}}_{\mathbf{j}}$, you have an estimate of its value to you, ${\mathbf{v}}_{\mathbf{j}}$. For any two garage sales you have an estimate of the transportation cost ${\mathbf{d}}_{\mathbf{ij}}$of getting from ${\mathbf{g}}_{\mathbf{i}}$to ${\mathbf{g}}_{\mathbf{j}}$. You are also given the costs ${\mathbf{d}}_{\mathbf{0}\mathbf{j}}$and ${\mathbf{d}}_{\mathbf{j}\mathbf{0}}$of going between your home and each garage sale. You want to find a tour of a subset of the given garage sales, starting and ending at home, that maximizes your total benefit minus your total transportation costs. Give an algorithm that solves this problem in time $\mathbf{O}\mathbf{}\left(n^2{2}^n\right)$.

(Hint: This is closely related to the traveling salesman problem.)

Short answer

This problem is identical to that of Traveling salesman problem where need to add one variant to it, that is to find relevant benefit by computing optimal distance. This problem is solved by dynamic programming approach.

Step-by-step solution

Dynamic programming approach.

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Algorithm for traveling salesman problem.

Let G be the garage is ${\mathrm{g}}_1,{\mathrm{g}}_2,{\mathrm{g}}_3...........{\mathrm{g}}_{\mathrm{n}}$and the P (G,j) is the gain function. Also assume that $\text{'}\mathrm{j}\text{'}$is the last garage we will visit before we reach back to origin.

Given: ${\mathrm{d}}_{0\mathrm{j}}$is the transportation cost from traveling ${\mathrm{g}}_{\mathrm{i}}\mathrm{to}{\mathrm{g}}_{\mathrm{j}}$to . Then compute Maximum of (${\mathrm{g}}_{\mathrm{j}}-{\mathrm{d}}_{0\mathrm{j}}$)

If${\mathrm{v}}_{\mathrm{i}}$ is the gain from garage ${\mathrm{g}}_{\mathrm{i}}$. Then, the base case, $\mathrm{P}\left(0,\mathrm{j}\right)={\mathrm{v}}_{\mathrm{j}}-{\mathrm{d}}_{0\mathrm{j}}$. This means the garage salesman have travel from origin is the starting point to garage${\mathrm{g}}_{\mathrm{j}}$.

, This is the recursive equation.

$\mathrm{P}\left(\mathrm{G},\mathrm{j}\right)=\max \left(\mathrm{P}\left(\mathrm{G}-{\mathrm{g}}_{\mathrm{i},}\mathrm{i}\right)+{\mathrm{p}}_{\mathrm{j}}-{\mathrm{d}}_{\mathrm{ij}}\right)$

$$\begin{gathered} \mathrm{P}\left(\left\{0\right\},1\right)={\mathrm{V}}_{\mathrm{J}}-{\mathrm{d}}_{0\mathrm{j}} \\ \mathrm{for}\left(\mathrm{s}=2\mathrm{to}\mathrm{n}\right) \\ \mathrm{P}\left(\mathrm{G},1\right)=\infty \\ \mathrm{for}\left(\mathrm{j}=1\mathrm{to}\mathrm{n}\right) \\ \mathrm{P}\left(\mathrm{G},1\right)=\max \left(\mathrm{P}\left(\mathrm{G}-{\mathrm{g}}_{\mathrm{i}}\mathrm{i}\right)+{\mathrm{p}}_{\mathrm{j}}-{\mathrm{d}}_{\mathrm{ij}}\right) \\ \mathrm{return}\mathrm{P}\left(\mathrm{G},\mathrm{j}\right) \end{gathered}$$

Hence by using, the algorithm which is closely related to the traveling salesman problem in which the shortest distance is to find between the starting node as source node to the end node called as destination node. For each garage sale ${\mathrm{g}}_{\mathrm{j}}$, you have an estimate of its value to you,$v_j$. For any two garage sales you have an estimate of the transportation cost ${\mathrm{d}}_{\mathrm{ij}}$of getting from ${\mathrm{g}}_{\mathrm{i}}\mathrm{to}{\mathrm{g}}_{\mathrm{j}}$.tour of a subset of the given garage sales, starting and ending at home is evaluated.

So, In this problem, the number of sub problems are $\left({\mathrm{n}}^2{2}^{\mathrm{n}}\right)$and to solve each sub problem, it takes time. So, total complexity is $O\left({\mathrm{n}}^2{2}^{\mathrm{n}}\right)$.