| Chemotaxis can provide biological organisms with good solutions to the travelling salesman problem. | |
| | |
MedLine Citation:
|
PMID: 21728597 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
The ability to find good solutions to the traveling salesman problem can benefit some biological organisms. Bacterial infection would, for instance, be eradicated most promptly if cells of the immune system minimized the total distance they traveled when moving between bacteria. Similarly, foragers would maximize their net energy gain if the distance that they traveled between multiple dispersed prey items was minimized. The traveling salesman problem is one of the most intensively studied problems in combinatorial optimization. There are no efficient algorithms for even solving the problem approximately (within a guaranteed constant factor from the optimum) because the problem is nondeterministic polynomial time complete. The best approximate algorithms can typically find solutions within 1%-2% of the optimal, but these are computationally intensive and can not be implemented by biological organisms. Biological organisms could, in principle, implement the less efficient greedy nearest-neighbor algorithm, i.e., always move to the nearest surviving target. Implementation of this strategy does, however, require quite sophisticated cognitive abilities and prior knowledge of the target locations. Here, with the aid of numerical simulations, it is shown that biological organisms can simply use chemotaxis to solve, or at worst provide good solutions (comparable to those found by the greedy algorithm) to, the traveling salesman problem when the targets are sources of a chemoattractant and are modest in number (n < 10). This applies to neutrophils and macrophages in microbial defense and to some predators. |
| | |
Authors:
|
A M Reynolds |
Related Documents
:
|
1805667 - Parasitology collections in museum. 7354627 - An analysis of connected speech samples of aphasic and normal speakers. 19185067 - Minimum information requirements: neither bandits in the attic nor bats in the belfry. 12132897 - On the parametrization of the toxicity of organic chemicals to tetrahymena pyriformis. ... 17678537 - A low-cost repellent for malaria vectors in the americas: results of two field trials i... 19771757 - Prevalence of occupational voice disorders in teachers. |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-5-9 |
Journal Detail:
|
Title: Physical review. E, Statistical, nonlinear, and soft matter physics Volume: 83 ISSN: 1550-2376 ISO Abbreviation: - Publication Date: 2011 May |
Date Detail:
|
Created Date: 2011-7-6 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101136452 Medline TA: Phys Rev E Stat Nonlin Soft Matter Phys Country: - |
Other Details:
|
Languages: ENG Pagination: 052901 Citation Subset: - |
Affiliation:
|
Rothamsted Research, Harpenden, Hertfordshire, AL5 2JQ, United Kingdom. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Subdiffusion on a fractal comb.
Next Document: Observation of the stabilizing effect of a laminated ablator on the ablative Rayleigh-Taylor instabi...